package body SList is
  function GetCourant (L: T_Liste) return T is
  begin
    return L.Val;
  end GetCourant;

--  function GetCourant (L: T_Liste) return access T is
--  begin
--  	return L.Val'Access;
--  end GetCourant;

  procedure SetCourant (L: in out T_Liste; Elem : in T) is
  begin
  	L.Val := Elem;
  end SetCourant;

  function GetSuite (L: T_Liste) return T_Liste is
  begin
    return L.Suiv;
  end GetSuite;
  
  procedure Modifier_Element (L : in out T_Liste) is
  begin
    Proc(L.Val);
  end Modifier_Element;
  
  procedure Vider (L : out T_Liste) is
  begin
    L := Cree_SListe;
  end Vider;
  
  procedure Ajout_Tete (L: in out T_Liste; N: in T) is
     Elem: T_Liste;
  begin
     Elem := new Cell;
     Elem.Val := N;
     Elem.Suiv := L;
     L := Elem;
  end Ajout_Tete;
  
  procedure Ajout_Apres (L: in out T_Liste; N: in T) is
  begin
  	Ajout_Tete (L.Suiv, N);
  end Ajout_Apres;
  
  function Ajout_Tete (L: T_Liste; N: T) return T_Liste is
    LNew: T_Liste := L;
  begin
    Ajout_Tete(LNew, N);
    return LNew;
  end Ajout_Tete;
  
  procedure Ajout_Fin (L: in out T_Liste; N: in T) is
    Elem, Courant, Preced: T_Liste;
  begin
    Courant := L; Preced := null;
    while Courant /= null loop
        Preced := Courant;
        Courant := Courant.Suiv;
    end loop;
    -- Courant = null
    
    Elem := new Cell;
    Elem.Val := N;
    Elem.Suiv := null;
    if Preced /= null then
        Preced.Suiv := Elem;
    else
        L := Elem;
    end if;
  end Ajout_Fin;
  
  function Cherche (L: T_Liste) return T_Liste is
    Courant: T_Liste;
  begin
    Courant := L;
    while (Courant /= null) and then (not Callback(Courant.Val)) loop
        Courant := Courant.Suiv;
    end loop;
    -- Courant = null or else Courant.Val = N
    return Courant;
  end;
  
  procedure Modifier (L: in out T_Liste) is
    function Cherche_Element is new Cherche(Callback);
    Elem : T_Liste;
  begin
    Elem := Cherche_Element(L);
    Proc(Elem.Val);
  end Modifier;
  
  procedure Extraire (L1: in out T_Liste; L2: out T_Liste) is
    Courant, Preced: T_Liste;
  begin
    L2 := Cree_SListe;
    
    Courant := L1;
    Preced := L1;
    
    while (Courant /= Null) loop

        if Callback(GetCourant(Courant)) then
            Ajout_Tete(L2, GetCourant(Courant));

            if L1 = Courant then
                L1 := Courant.Suiv;
            else
                Preced.Suiv := Courant.Suiv;
            end if;
        else
            Preced := Courant;
        end if;
        
        Courant := Courant.Suiv;
    end loop;
  end Extraire;

  procedure Sousliste (L1: in T_Liste; L2: out T_Liste) is
    Courant: T_Liste;
  begin
    L2 := Cree_SListe;
    
    Courant := L1;
    while (Courant /= Null) loop

        if Callback(GetCourant(Courant)) then
            Ajout_Tete(L2, GetCourant(Courant));
        end if;        
        Courant := Courant.Suiv;
    end loop;
  end Sousliste;
  
  procedure Supprime_Suivant (L: in out T_Liste) is
  begin
  	L := L.Suiv;
  end Supprime_Suivant;
  
  -- A revoir
  procedure Supprime (L : in out T_Liste; Elem : out T) is
    Courant, Preced : T_Liste;
  begin
    Courant := L;
    while (Courant /= null) and then (not Callback(Courant.Val)) loop
        Preced := Courant;
        Courant := Courant.Suiv;
    end loop;
    if Courant /= null then
        if Courant = L then
            -- L'entier N se trouve en premiere position
            L := Courant.Suiv;
        else
            -- Cas general
            Preced.Suiv := Courant.Suiv;
        end if;
        Elem := Courant.Val;
    end if;
  end Supprime;
  
  --function Supprime (L : in out T_Liste) return T is
  
  
  procedure Supprime_1 (L: in out T_Liste; N: in T) is
    Courant, Preced: T_Liste;
  begin
    Courant := L;
    while (Courant /= null) and then (Courant.Val /= N) loop
        Preced := Courant;
        Courant := L.Suiv;
    end loop;

    if Courant /= null then
        if Courant = L then
            -- L'entier N se trouve en premiere position
            L := Courant.Suiv;
        else
            -- Cas general
            Preced.Suiv := Courant.Suiv;
        end if;
        Courant := null;
    end if;
  end;
  
  procedure Tri (L: in out T_Liste) is
    Courant : T_Liste; Succ : T_Liste; Pred : T_Liste := Null; Echange : boolean := True;
  begin
    while Echange loop
        Echange := False;
        Courant := L; Pred := Null;
        while (Courant /= Null and then Courant.Suiv /= Null) loop
            if (Callback(Courant.Val, Courant.Suiv.Val)) then
                
                Echange := True;    
                
                Succ := Courant.Suiv;
                
                Courant.Suiv := Succ.Suiv;
                Succ.Suiv := Courant;
                
                if Pred /= Null then
                    Pred.Suiv := Succ;
                else
                    L := Succ;
                end if;
                
                Pred := Succ;
            else
                Pred := Courant;
                Courant := Courant.Suiv;
            end if;
            
        end loop;
      end loop;
  end Tri;

  procedure Map(L : in out T_Liste) is
    Courant : T_Liste := L;
  begin
    while not Est_Vide(Courant) loop
        Proc(Courant.Val);
        Courant := GetSuite(Courant);
    end loop;
  end Map;

  procedure Foreach(L : in T_Liste) is
    Courant : T_Liste := L;
  begin
    while not Est_Vide(Courant) loop
        Proc(Courant.Val);
        Courant := GetSuite(Courant);
    end loop;
  end Foreach;
  
  function Copie_Triee(L: T_Liste) return T_Liste is
    Courant: T_Liste;
    Triee : T_Liste := Cree_SListe;
    
        procedure AjoutCroissant(L: in out T_Liste; N: in T) is
            Courant, Preced, Elem: T_Liste;
        begin
            Courant := L; Preced := null;
            while (Courant /= null) and then (Callback(Courant.Val,N)) loop
                Preced := Courant;
                Courant := Courant.Suiv;
            end loop;
            -- Courant = null or else Courant.Val >= N
            Elem := new Cell'(Val=>N, Suiv=>Courant);
            
            if (Preced = null) then
                L := Elem;
            else
                Preced.Suiv := Elem;
            end if;
        end AjoutCroissant;
    
  begin
    Courant := L;
    while Courant /= null loop
        AjoutCroissant(Triee, Courant.Val);
        Courant := Courant.Suiv;
    end loop;
    
    return Triee;
  end Copie_Triee;
  
   function Est_Vide(t: T_Liste) return Boolean is
   begin
      return T=null;
   end Est_Vide;

   function Cree_SListe return T_Liste is
      L: T_Liste:= null;
   begin
      return L;
   end Cree_SListe;


    function Copie(T: T_Liste) return T_Liste is
        R : T_Liste := Cree_SListe;
        CourantT : T_Liste := T;
        CourantR : T_Liste := Null;
    begin
        while CourantT /= Null loop
            if CourantR = Null then
                Ajout_Tete(CourantR, CourantT.Val);
                R := CourantR;
            else
                Ajout_Tete(CourantR.Suiv, CourantT.Val);
                CourantR := CourantR.Suiv;
            end if;
            CourantT := CourantT.Suiv;
        end loop;
        
        return R;
    end Copie;
end SList;
